package 极客算法训练营.chapter07;

public class 二叉树的最近公共祖先 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            //如果没找到，就向上返回空
            if (root == null) return null;
            //如果找到p，就一直向上返回；q同理
            if (root == p || root == q) return root;
            //遍历左右结点
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            //如果它的左右结点都不为空，说明p，q分别在它的左右子树中，当前结点就是最近祖先，一直向上返回就行，直到回溯到根节点
            if (left != null && right != null) return root;
            //如果left为空，就返回right；right也为空时，左右都为null，返回哪个都一样
            return left == null ? right : left;
        }
    }
}
